package agorithm.week1.classTwo;

import java.util.Deque;
import java.util.LinkedList;

/**
 *
 题目描述
 评论 (187)
 题解 (233)
 提交记录
 1109. 航班预订统计
 这里有 n 个航班，它们分别从 1 到 n 进行编号。

 有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

 请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。



 示例 1：

 输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
 输出：[10,55,45,25,25]
 解释：
 航班编号        1   2   3   4   5
 预订记录 1 ：   10  10
 预订记录 2 ：       20  20
 预订记录 3 ：       25  25  25  25
 总座位数：      10  55  45  25  25
 因此，answer = [10,55,45,25,25]
 示例 2：

 输入：bookings = [[1,2,10],[2,2,15]], n = 2
 输出：[10,25]
 解释：
 航班编号        1   2
 预订记录 1 ：   10  10
 预订记录 2 ：       15
 总座位数：      10  25
 因此，answer = [10,25]


 提示：

 1 <= n <= 2 * 104
 1 <= bookings.length <= 2 * 104
 bookings[i].length == 3
 1 <= firsti <= lasti <= n
 1 <= seatsi <= 104
 */
public class CorpFlightBookings {
    public static void main(String[] args) {
        Deque<Integer> stack = new LinkedList<>();
        stack.peekFirst();
        stack.pollFirst();
        stack.addFirst(1);
        stack.peekLast();
        stack.pollLast();
        stack.addLast(2);
        stack.isEmpty();
        int[][] digits = {{1,2,10},{2,3,20},{2,5,25}};
        int[] arr = corpFlightBookings(digits,5);
        System.out.println("max = " + arr);
    }

    public static int[] corpFlightBookings(int[][] bookings, int n) {
        // 差分 求前缀和 就是原数组
        // 原数组 求前缀和 得到前缀和数组
        // 前缀和数组 求差分 得到原数组
        //  差分 第i个数+，然后第j+1个数-适用于区间定+定减
        int[] c = new int[n + 1];
        // 求差分数组
        for( int i = 0; i< bookings.length ; i++){
            c[bookings[i][0]-1] += bookings[i][2];
            c[bookings[i][1]] -= bookings[i][2];
            // System.out.println(c[0]+";"+c[1]+";"+c[2]+";"+c[3]+";"+c[4]+";"+c[5]+";");
        }
        // 求前缀和
        int[] answer  = new int[n];
        answer[0] = c[0];
        for( int i = 1; i< n; i++){
            answer[i] += answer[i-1] + c[i];
        }
        return answer;
    }
}
